﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>

using namespace std;

int result = 0;
vector<int> a;//存队员的要求
vector<int> exist;//表示哪个队员已经排队了
int res;//存结果
int n;

void dfs(int pos)//pos表示下一个存的位置
{
    if (pos == a.size())//存放成功
    {
        ++res;
        return;
    }

    for (int i = 1; i < n + 1; ++i)//pos位置，枚举看有多少队员可以排队，再深度递归进去
    {
        if (exist[i])//当前队员已经排队了
            continue;
        if (exist[a[i]])//当前队员i要求排在a[i]的后面，但是a[i]已经排队了，不管队员i怎么选择，都是不满足要求的，直接return
            return;
        exist[i] = 1;//表示i排在pos位置
        dfs(pos + 1);
        exist[i] = 0;//回溯
    }
}

int main()
{
    n = 0;
    cin >> n;

    a.assign(n + 1, 0);
    exist.assign(n + 1, 0);
    for (int i = 1; i <= n; ++i)//统一下标，因为a[i]表示排在某个队员后面，是从1开始的
    {
        cin >> a[i];
    }

    dfs(1);//递归枚举所有可能的情况

    cout << res << endl;
    return 0;
}

/*
链接：https://ac.nowcoder.com/acm/problem/229386
来源：牛客网

题目描述
dd作为体操队队长，在给队员们排队形，体操队形为一个单独的纵列，
体操队有n个同学，标号为1∼n，对于𝑖(1≤i≤n)号队员，会有一个诉求(1≤a[i]≤n)，
表示他想排在a[i]号队员前面，当a[i]=i时，我们认为他没有位置需求，随便排哪儿都行，
dd想知道有多少种队形方案，可以满足所有队员的要求。
输入描述:
读入第一行一个数字n(2≤n≤10)
第二行n个数字，表示a[i],保证1≤a[i]≤n
输出描述:
输出一行，表示方案数

示例1
输入
3
1 1 2
输出
1
*/

